package com.yubest;

/**
 * 前驱节点：对一棵二叉树进行中序遍历，遍历后的顺序，当前节点的前一个节点为该节点的前驱节点；
 * 后继节点：对一棵二叉树进行中序遍历，遍历后的顺序，当前节点的后一个节点为该节点的后继节点；
 * 例如一颗完全二叉树（1,2,3,4,5,6,7） [图片] img/morris.png ，按照中序遍历后的顺序为：（4,2,5,1,6,3,7），1节点的前驱节点为：5，后继节点为6
 *
 * Morris遍历：
 *
 * 假设当前节点为cur。
 * 1、如果cur无左孩子，cur向右移动（cur=cur.right）
 * 2、如果cur有左孩子，找到cur左子树上最右的节点(前驱节点)，记为pre
 *     2.1、如果pre的right指针指向空，让其指向cur，cur向左移动（cur=cur.left）
 *     2.2、如果pre的right指针指向cur，让其指向空，cur向右移动（cur=cur.right）
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/11/12 9:54
 */
public class MorrisTraversal {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1,
                new TreeNode(2,
                        new TreeNode(4),
                        new TreeNode(5)),
                new TreeNode(3,
                        new TreeNode(6),
                        new TreeNode(7)));

        System.out.println("Morris序：");
        new MorrisTraversal().morris(root);

        System.out.println("\n\n前序：");
        new MorrisTraversal().preorderTraversal(root);

        System.out.println("\n\n中序：");
        new MorrisTraversal().inorderTraversal(root);

        System.out.println("\n\n后序：");
        new MorrisTraversal().postorderTraversal(root);
    }

    /**
     * morris 遍历
     *
     * 特性：有左子节点的当前节点，都会被遍历到2次
     *
     * @param root
     */
    public void morris(TreeNode root) {
        //当前操作节点
        TreeNode cur = root;
        //前驱节点，左子节点的最后子节点
        TreeNode pre;
        while (null != cur) {
            System.out.print(cur.val + " ");
            pre = cur.left;
            //如果左节点非空
            if (null != pre) {
                //找到前驱节点，即左节点的最右节点
                while (null != pre.right && pre.right != cur) {
                    pre = pre.right;
                }
                //如果前驱节点的右子节点为空
                if (null == pre.right) {
                    pre.right = cur;
                    //当前操作节点左移
                    cur = cur.left;
                } else {
                    pre.right = null;
                    //当前操作节点右移
                    cur = cur.right;
                }
            } else {
                //当前操作节点右移
                cur = cur.right;
            }
        }
    }

    /**
     * 前序遍历：打印的时机，在morris遍历时，cur向左或者右子节点移动之前
     * @param root
     */
    public void preorderTraversal(TreeNode root) {
        TreeNode cur = root;
        TreeNode pre;
        while (null != cur) {
            pre = cur.left;
            if (null != pre) {
                while (null != pre.right && pre.right != cur) {
                    pre = pre.right;
                }
                if (null == pre.right) {
                    System.out.print(cur.val + " ");
                    pre.right = cur;
                    cur = cur.left;
                } else {
                    pre.right = null;
                    cur = cur.right;
                }
            } else {
                System.out.print(cur.val + " ");
                cur = cur.right;
            }
        }
    }

    /**
     * 中序遍历：打印的时机，在morris遍历时，cur向右子节点移动之前
     * @param root
     */
    public void inorderTraversal(TreeNode root) {
        TreeNode cur = root;
        TreeNode pre;
        while (null != cur) {
            pre = cur.left;
            if (null != pre) {
                while (null != pre.right && pre.right != cur) {
                    pre = pre.right;
                }
                if (null == pre.right) {
                    pre.right = cur;
                    cur = cur.left;
                } else {
                    System.out.print(cur.val + " ");
                    pre.right = null;
                    cur = cur.right;
                }
            } else {
                System.out.print(cur.val + " ");
                cur = cur.right;
            }
        }
    }

    /**
     * 后序遍历：打印的时机，在morris遍历时，在第二次回到当前节点时，反转当前结点的左子结点到前驱结点之间的路径，输出该路径所有结点
     *
     * @param root
     */
    public void postorderTraversal(TreeNode root) {
        //定义哨兵位
        TreeNode guard = new TreeNode(-1, root, null);
        TreeNode cur = guard;
        TreeNode pre;
        while (null != cur) {
            pre = cur.left;
            if (null != pre) {
                while (null != pre.right && pre.right != cur) {
                    pre = pre.right;
                }
                if (null == pre.right) {
                    pre.right = cur;
                    cur = cur.left;
                } else {
                    //反转当前结点的左子结点到前驱结点之间的路径，输出该路径所有结点
                    reverse(cur.left, pre);
                    //打印
                    TreeNode p = pre;
                    while (null != p) {
                        System.out.print(p.val + " ");
                        if (p == cur.left) {
                            break;
                        }
                        p = p.right;
                    }
                    //恢复反转
                    reverse(pre, cur.left);
                    pre.right = null;
                    cur = cur.right;
                }
            } else {
                cur = cur.right;
            }
        }
    }

    /**
     * 反转链表
     * @param start
     * @param end
     */
    private void reverse(TreeNode start, TreeNode end) {
        if (start == end) {
            return;
        }
        //前一个节点
        TreeNode pre = null;
        //当前节点
        TreeNode cur = start;
        //后一个节点
        TreeNode next;
        while (true) {
            next = cur.right;
            cur.right = pre;
            pre = cur;
            if (cur == end) {
                break;
            }
            cur = next;
        }

    }

}
